package LeetCode.Arrays;

import java.util.Arrays;

/**
 * @author : LdLtd
 * @Date : 2023/8/5
 * @Description:189. 轮转数组
 */
public class rotate_array {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3,4,5,6};
        int k = 3;
        solution.rotate(nums,k);
        System.out.println(Arrays.toString(nums));
    }
    static class Solution {
        public void rotate(int[] nums, int k) {
            int t=0;
            int n=nums.length;
            k=k%n;
            int i=-1,tem=0,pre=0,len=n;
            while (len>0){
                i++;
               t=i;
                pre=nums[i];
                do{
                    //保留现在值
                    tem=nums[(t+k)%n];
                    //改变现在的值
                    nums[(t+k)%n]=pre;
                    //保留现在的值
                    pre=tem;
                    t+=k;
                    len--;
                }while ((t)%n!=i);
            }
        }
/*官方写法*/
        public void rotate1(int[] nums, int k) {
            int n = nums.length;
            k = k % n;
            int count = gcd(k, n);
            for (int start = 0; start < count; ++start) {
                int current = start;
                int prev = nums[start];
                do {
                    int next = (current + k) % n;
                    int temp = nums[next];
                    nums[next] = prev;
                    prev = temp;
                    current = next;
                } while (start != current);
            }
        }

        public int gcd(int x, int y) {
            return y > 0 ? gcd(y, x % y) : x;
        }


        /*翻转解法
        * 首先对整个数组实行翻转，这样子原数组中需要翻转的子数组，就会跑到数组最前面。
          这时候，从 kkk 处分隔数组，左右两数组，各自进行翻转即可。*/
        public void rotate2(int[] nums, int k) {
            k %= nums.length;
            reverse(nums, 0, nums.length - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length - 1);
        }
        public void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start += 1;
                end -= 1;
            }
        }

    }
}
